﻿//#include <iostream>
//#include <algorithm>
//using namespace std;
//
//const long long N = 2 * 1e5 + 10;
//typedef pair<long long, long long> PII;
//PII arr[N];
//long long n;
//
//int main()
//{
//    cin >> n;
//    for (long long i = 0; i < n; i++)
//        cin >> arr[i].first >> arr[i].second;
//    sort(arr, arr + n);
//    long long cnt = 1, prev = arr[0].second;
//    for (long long i = 1; i < n; i++)
//    {
//        if (arr[i].first >= prev)
//        {
//            cnt++;
//            prev = arr[i].second;
//        }
//        else
//            prev = min(prev, arr[i].second);
//    }
//    std::cout << cnt << std::endl;
//}




//#include <iostream>
//using namespace std;
//typedef long long LL;
//const int N = 55, M = 15;
//const LL INF = 0x3f3f3f3f3f3f3f3f;
//int n, k, d;
//LL arr[N];
//LL f[N][M], g[N][M];
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >> arr[i];
//	cin >> k >> d;
//	// 初始化放在填表中进⾏了
//	for (int i = 1; i <= n; i++) // 填写每⼀⾏
//	{
//		g[i][1] = f[i][1] = arr[i];
//		for (int j = 2; j <= min(i, k); j++) // 挑选⼏个⼈
//		{
//			f[i][j] = -INF; // 初始化
//			g[i][j] = INF; // 初始化
//			for (int prev = max(i - d, j - 1); prev <= i - 1; prev++) // 前⾯挑选
//				的最后⼀个位置
//			{
//			f[i][j] = max(max(f[prev][j - 1] * arr[i], g[prev][j - 1] *
//		   arr[i]), f[i][j]);
//			g[i][j] = min(min(f[prev][j - 1] * arr[i], g[prev][j - 1] *
//		   arr[i]), g[i][j]);
//			}
//		}
//	}
//	LL ret = -INF;
//	for (int i = k; i <= n; i++) ret = max(ret, f[i][k]);
//	cout << ret << endl;
//	return 0;
//}


//long long change(string s)
//{
//	for (int i = s.size() - 2; i >= 0; i--)
//	{
//		s += s[i];
//	}
//	return stol(s);
//}
//bool isprim(long long x)
//{
//	if (x <= 1) return false;
//	for (long long i = 2; i <= sqrt(x); i++)
//	{
//		if (x % i == 0) return false;
//	}
//	return true;
//}
//int main()
//{
//	string s;
//	cin >> s;
//	long long x = change(s);
//	if (isprim(x)) cout << "prime" << endl;
//	else cout << "noprime" << endl;
//	return 0;
//}



//#include <iostream>
//#include <string>
//using namespace std;
//int main()
//{
//	string s;
//	cin >> s;
//	int sum = 0, count = 1, n = s.size();
//	for (int i = 0; i < n - 1; i++)
//	{
//		if (s[i] >= '0' && s[i] <= '9')
//		{
//			sum += (s[i] - '0') * count;
//			count++;
//		}
//	}
//	sum %= 11;
//	if (sum == s[n - 1] - '0' || (sum == 10 && s[n - 1] == 'X'))
//	{
//		cout << "Right" << endl;
//	}
//	else
//	{
//		s[n - 1] = sum == 10 ? 'X' : sum + '0';
//		cout << s << endl;
//	}
//	return 0;
//}




//#include <iostream>
//#include <cstring>
//#include <queue>
//using namespace std;
//const int N = 35;
//int x1, y1; // 标记起点位置
//int n, m;
//char arr[N][N];
//int dist[N][N];
//queue<pair<int, int>> q;
//int dx[4] = { 0, 0, 1, -1 };
//int dy[4] = { 1, -1, 0, 0 };
//void bfs()
//{
//	memset(dist, -1, sizeof dist);
//	dist[x1][y1] = 0;
//	q.push({ x1, y1 });
//
//	while (q.size())
//	{
//		auto [x2, y2] = q.front();
//		q.pop();
//		for (int i = 0; i < 4; i++)
//		{
//			int a = x2 + dx[i], b = y2 + dy[i];
//			if (a >= 1 && a <= n && b >= 1 && b <= m && dist[a][b] == -1 &&
//				arr[a][b] != '*')
//			{
//				dist[a][b] = dist[x2][y2] + 1;
//				if (arr[a][b] != 'e')
//				{
//					q.push({ a, b });
//				}
//			}
//		}
//	}
//}
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			cin >> arr[i][j];
//			if (arr[i][j] == 'k')
//			{
//				x1 = i, y1 = j;
//			}
//		}
//	}
//	bfs();
//
//	int count = 0, ret = 1e9;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			if (arr[i][j] == 'e' && dist[i][j] != -1)
//			{
//				count++;
//				ret = min(ret, dist[i][j]);
//			}
//		}
//	}
//	if (count == 0) cout << -1 << endl;
//	else cout << count << " " << ret << endl;
//
//	return 0;
//}



class Solution
{
	int m, n;
	int dx[4] = { 0, 0, 1, -1 };
	int dy[4] = { 1, -1, 0, 0 };
	int memo[1010][1010];
	int dfs(vector<vector<int> >& matrix, int i, int j)
	{
		if (memo[i][j] != -1) return memo[i][j];
		int len = 1;
		for (int k = 0; k < 4; k++)
		{
			int x = i + dx[k], y = j + dy[k];
			if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i]
				[j])
			{
				len = max(len, 1 + dfs(matrix, x, y));
			}
		}
		memo[i][j] = len;
		return len;
	}
public:
	int solve(vector<vector<int> >& matrix)
	{
		m = matrix.size(), n = matrix[0].size();
		memset(memo, -1, sizeof memo);
		int ret = 1;
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				ret = max(ret, dfs(matrix, i, j));
			}
		}
		return ret;
	}
};